1089. 复写零【简单】

• 1. 📝 题目描述
• 2. 🎯 s.1 - 双指针（末尾写入）

1. 📝 题目描述

• leetcode

给你一个长度固定的整数数组 arr，请你将该数组中出现的每个零都复写一遍，并将其余的元素向右平移。

注意：请不要在超过该数组长度的位置写入元素。请对输入的数组就地进行上述修改，不要从函数返回任何东西。

---

示例 1：

输入：arr = [1,0,2,3,0,4,5,0]
输出：[1,0,0,2,3,0,0,4]

解释：
调用函数后，输入的数组将被修改为：[1,0,0,2,3,0,0,4]

---

示例 2：

输入：arr = [1,2,3]
输出：[1,2,3]

解释：
调用函数后，输入的数组将被修改为：[1,2,3]

---

提示：

• 1 <= arr.length <= 10^4
• 0 <= arr[i] <= 9

2. 🎯 s.1 - 双指针（末尾写入）

js

/**
 * @param {number[]} arr
 * @return {void}
 */
var duplicateZeros = function (arr) {
  let zeros = 0
  const n = arr.length
  for (let i = 0; i < n; i++) if (arr[i] === 0) zeros++
  let i = n - 1
  let j = n + zeros - 1
  while (i >= 0) {
    if (arr[i] !== 0) {
      if (j < n) arr[j] = arr[i]
      i--
      j--
    } else {
      // write two zeros
      if (j < n) arr[j] = 0
      j--
      if (j < n) arr[j] = 0
      j--
      i--
    }
  }
}

• 时间复杂度：$O(n)$，其中 $n$ 为数组长度，需先后遍历数组进行计数与移动
• 空间复杂度：$O(1)$，直接在输入数组上修改，不使用额外空间

算法思路：

• 统计数组中零的总数，计算复写后的虚拟总长度
• 从后向前遍历数组，根据虚拟索引将元素移动到最终位置
• 若当前元素为零，则连续进行两次写入操作并跳过越界位置